home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 422_02 / misc / bignum.c < prev    next >
C/C++ Source or Header  |  1994-03-20  |  7KB  |  298 lines
  1. /*
  2.  * This program demonstrates a method of performing basic arithmetic
  3.  * operations (+ - * / %) on arbitrarily long unsigned BINARY numbers.
  4.  *
  5.  * The arithmetic is performed using only SHIFT, ADD and SUBTRACT
  6.  * operations. These algorithms are ideally suitable for fast long
  7.  * math functions written in assembler. They operate quite slowly
  8.  * when written in 'C', due to the considerable overhead involved
  9.  * in simulating the "Carry bit", which is used used to propogate
  10.  * the multi-byte add, subtract and shifts.
  11.  *
  12.  * The numbers are stored and manipulated in memory based "registers".
  13.  * These registers are accessed a byte at a time, and are stored in
  14.  * "little endian" format (least significant byte occuring first in
  15.  * memory). This is done for two reasons:
  16.  *        1 - It makes it easier for most of the functions to manupulate
  17.  *            the register.
  18.  *        2 - It makes it easy to define small constants in 'C', due to
  19.  *            the automatic zero filling on the right.
  20.  *                eg: unsigned char BIG_ONE[BIG_WIDTH] = { 1 };
  21.  *
  22.  * Copyright 1993-1994 Dave Dunfield
  23.  * All rights reserved.
  24.  *
  25.  * Compile command: cc bignum -fop
  26.  */
  27. #include <stdio.h>
  28.  
  29. /*
  30.  * To work with larger/smaller numbers, change this constant
  31.  */
  32. #define    BIG_WIDTH    8        /* 8 bytes (64 bits) */
  33.  
  34. /*
  35.  * This temporary register will contain the REMAINDER after a division,
  36.  * and also a second copy of the product after a multiplication.
  37.  */
  38. unsigned char big_temp[BIG_WIDTH];
  39.  
  40. /*
  41.  * Add two BIG values: n1 += n2
  42.  * Returns carry out of big addition.
  43.  */
  44. unsigned big_add(n1, n2)
  45.     unsigned char *n1, *n2;
  46. {
  47.     unsigned i, t;
  48.  
  49.     i = BIG_WIDTH;
  50.     t = 0;
  51.     do {
  52.         t = (unsigned)*n1 + (unsigned)*n2++ + t;
  53.         *n1++ = t;
  54.         t = t >> 8; }
  55.     while(--i);
  56.     return t;
  57. }
  58.  
  59. /*
  60.  * Subtract two BIG values: n1 -= n2
  61.  * Returns borrow out of big subtraction.
  62.  */
  63. unsigned big_sub(n1, n2)
  64.     unsigned char *n1, *n2;
  65. {
  66.     unsigned i, t;
  67.  
  68.     i = BIG_WIDTH;
  69.     t = 0;
  70.     do {
  71.         t = (unsigned)*n1 - (unsigned)*n2++ - t;
  72.         *n1++ = t;
  73.         t = (t >> 8) ? 1 : 0; }
  74.     while(--i);
  75.     return t;
  76. }
  77.  
  78. /*
  79.  * Shift a BIG value right: n1 >>= 1
  80.  * 'c' is the carry in (1/0 shifted in on left)
  81.  * Returns carry out of big shift.
  82.  */
  83. unsigned char big_shift_right(n1, c)
  84.     unsigned char *n1, c;
  85. {
  86.     unsigned i;
  87.     unsigned char c1;
  88.  
  89.     i = BIG_WIDTH;
  90.     do {
  91.         c1 = n1[--i];
  92.         n1[i] = (c1 >> 1) | (c ? 0x80 : 0);
  93.         c = c1 & 0x01; }
  94.     while(i);
  95.     return c;
  96. }
  97.  
  98. /*
  99.  * Shift a BIG value left: n1 <<= 1
  100.  * 'c' is the carry in (1/0 shifted in on right)
  101.  * Returns carry out of big shift.
  102.  */
  103. unsigned char big_shift_left(n1, c)
  104.     unsigned char *n1, c;
  105. {
  106.     unsigned i;
  107.     unsigned char c1;
  108.  
  109.     i = 0;
  110.     do {
  111.         c1 = n1[i];
  112.         n1[i] = (c1 << 1) | (c ? 0x01 : 0);
  113.         c = c1 & 0x80; }
  114.     while(++i < BIG_WIDTH);
  115.     return c;
  116. }
  117.  
  118. /*
  119.  * Test a BIG value for ZERO
  120.  */
  121. int big_test(n1)
  122.     unsigned char *n1;
  123. {
  124.     unsigned i;
  125.  
  126.     i = BIG_WIDTH;
  127.     do {
  128.         if(*n1++)
  129.             return 1; }
  130.     while(--i);
  131.     return 0;
  132. }
  133.  
  134. /*
  135.  * Compare two BIG values. Return 1 if n1 < n2
  136.  */
  137. int big_compare(n1, n2)
  138.     unsigned char *n1, *n2;
  139. {
  140.     unsigned i;
  141.  
  142.     n1 += (i = BIG_WIDTH);
  143.     n2 += BIG_WIDTH;
  144.     do {
  145.         if(*--n1 != *--n2)
  146.             return *n1 < *n2; }
  147.     while(--i);
  148.     return 0;
  149. }
  150.  
  151. /*
  152.  * Multiply two BIG values: n1 *= n2
  153.  * Product is also stored in big_temp
  154.  */
  155. big_mul(n1, n2)
  156.     unsigned char *n1, *n2;
  157. {
  158.     unsigned char n3[BIG_WIDTH];
  159.  
  160.     /* Use a local copy of 'n2' to avoid destroying the original */
  161.     memset(big_temp, 0, sizeof(big_temp));
  162.     memcpy(n3, n2, sizeof(n3));
  163.  
  164.     do {
  165.         if(big_shift_right(n1, 0))
  166.             big_add(big_temp, n3);
  167.         if(!big_test(n1))
  168.             break;
  169.         big_shift_left(n3, 0); }
  170.     while(big_test(n3));
  171.  
  172.     memcpy(n1, big_temp, sizeof(big_temp));
  173. }
  174.  
  175. /*
  176.  * Perform a BIG divide: n1 /= n2
  177.  * Remainder is stored in big_temp
  178.  */
  179. big_div(n1, n2)
  180.     unsigned char *n1, *n2;
  181. {
  182.     unsigned t, cy;
  183.  
  184.     memset(big_temp, 0, sizeof(big_temp));
  185.     t = (BIG_WIDTH*8) + 1;
  186.  
  187. carry_zero:
  188.     cy = 0;
  189.     for(;;) {
  190.         cy = big_shift_left(n1, cy);
  191.         if(!--t)
  192.             return;
  193.         big_shift_left(big_temp, cy);
  194.         if(big_compare(big_temp, n2))
  195.             goto carry_zero;
  196.         big_sub(big_temp, n2);
  197.         cy = 1; }
  198. }
  199.  
  200. /*
  201.  * Convert BIG number to an ASCII string
  202.  */
  203. big_to_string(string, n1, base)
  204.     unsigned char *string, *n1, base;
  205. {
  206.     unsigned sp;
  207.     unsigned char n2[BIG_WIDTH], btemp[BIG_WIDTH], c, stack[(BIG_WIDTH*25)/10+1];
  208.  
  209.     /* Use a local copy of 'n1' to avoid destroying original */
  210.     memcpy(n2, n1, sizeof(n2));
  211.  
  212.     memset(btemp, sp = 0, sizeof(btemp));
  213.     *btemp = base;
  214.  
  215.     /* Stack up digits in reverse order */
  216.     do {
  217.         big_div(n2, btemp);
  218.         if((c = *big_temp + '0') > '9')
  219.             c += 7;
  220.         stack[sp++] = c; }
  221.     while(big_test(n2));
  222.     /* Unstack digits into output buffer */
  223.     do
  224.         *string++ = stack[--sp];
  225.     while(sp);
  226.     *string = 0;
  227. }
  228.  
  229. /*
  230.  * Parse a string into a BIG number
  231.  * Returns character terminating conversion (0 = end of string)
  232.  */
  233. char string_to_big(string, n1, base)
  234.     unsigned char *string, *n1, base;
  235. {
  236.     unsigned char btemp[BIG_WIDTH], c;
  237.  
  238.     memset(btemp, 0, sizeof(btemp));
  239.     memset(n1, 0, BIG_WIDTH);
  240.  
  241.     while(c = *string++) {
  242.         if(isdigit(c))            /* Decimal digit */
  243.             c -= '0';
  244.         else if(c >= 'a')        /* Lower-case alphabetic */
  245.             c -= ('a' - 10);
  246.         else if(c >= 'A')        /* Upper-case alphabetic */
  247.             c -= ('A' - 10);
  248.         else                    /* Error - Invalid digit */
  249.             break;
  250.         if(c >= base)            /* Error - out of range */
  251.             break;
  252.         *btemp = base;
  253.         big_mul(n1, btemp);        /* Make room */
  254.         *btemp = c;
  255.         big_add(n1, btemp); }    /* Add new digit */
  256.     return c;
  257. }
  258.  
  259.  
  260. /*
  261.  * Demo program... A simple BIG number command line calculator
  262.  */
  263. main(argc, argv)
  264.     int argc;
  265.     char *argv[];
  266. {
  267.     int i;
  268.     char output[(BIG_WIDTH*25)/10+1];
  269.     unsigned char buffer1[BIG_WIDTH], buffer2[BIG_WIDTH];
  270.  
  271.     if(argc < 2) {
  272.         fputs("\nUse: bignum <num> [+-*/% <num> ...]\n", stderr);
  273.         exit(-1); }
  274.  
  275.     /* Obtain first value from command line */
  276.     string_to_big(argv[1], buffer1, 10);
  277.  
  278.     /* For each operator/number, get value & perform operation */
  279.     for(i=2; i < argc; i += 2) {
  280.         string_to_big(argv[i+1], buffer2, 10);
  281.         switch(*argv[i]) {
  282.             case '+' :    big_add(buffer1, buffer2);    break;
  283.             case '-' :    big_sub(buffer1, buffer2);    break;
  284.             case '*' :    big_mul(buffer1, buffer2);    break;
  285.             case '/' :    big_div(buffer1, buffer2);    break;
  286.             case '%' :
  287.                 big_div(buffer1, buffer2);
  288.                 memcpy(buffer1, big_temp, sizeof(buffer1));
  289.                 break;
  290.             default:
  291.                 fputs("\nInvalid operator. Use: + - * / %\n", stderr);
  292.                 exit(-1); } }
  293.  
  294.     /* Display final result */
  295.     big_to_string(output, buffer1, 10);
  296.     printf("%s\n", output);
  297. }
  298.